package BinaryTree;

/**
 * 二叉树的Morris遍历
 *
 * @author Liaorun
 */
public class Morris {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    public static void morris(Node head) {
        if (head == null) {
            return;
        }

        Node cur = head;
        Node mostRight = null;


        while (cur != null) {
            // mostRight是cur左孩子
            mostRight = cur.left;

            if (mostRight != null) {
                // 有左子树
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }

                // mostRight变成了cur左子树上，最右的节点
                if (mostRight.right == null) {
                    // 第一次来到cur

                    // 该叶节点的右指针指向当前节点
                    mostRight.right = cur;
                    // 当前节点指针指向当前节点的左节点
                    cur = cur.left;
                    continue;
                } else {
                    // mostRight.right 已经指向当前节点，第二次来到当前节点
                    // 恢复原来的树形结构
                    mostRight.right = null;
                }
            }

            cur = cur.right;
        }
    }


    public static void morrisPre(Node head) {
        if (head == null) {
            return;
        }

        Node cur = head;
        Node mostRight = null;

        while (cur != null) {
            mostRight = cur.left;


            if (mostRight != null) {
                // 有左子树
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null) {

                    System.out.println(cur.value);
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    // 第二次来到当前节点
                    // 恢复原来的树形结构
                    mostRight.right = null;
                }
            } else {
                // 当前节点没有左子树的情况
                // 只能来到当前节点一次
                System.out.println(cur.value);
            }

            cur = cur.right;
        }
    }


    /**
     * 利用morris 进行中序遍历
     * 1. 没有左子树的节点只能到达一次，直接打印
     * 2. 有左子树的节点可以到达两次，第二次打印
     *
     * @param head 头节点
     */
    public static void morrisIn(Node head) {
        if (head == null) {
            return;
        }

        Node cur = head;
        Node mostRight = null;


        while (cur != null) {
            // mostRight是cur左孩子
            mostRight = cur.left;

            if (mostRight != null) {
                // 有左子树
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }

                // mostRight变成了cur左子树上，最右的节点
                if (mostRight.right == null) {
                    // 第一次来到cur

                    // 该叶节点的右指针指向当前节点
                    mostRight.right = cur;
                    // 当前节点指针指向当前节点的左节点
                    cur = cur.left;
                    continue;
                } else {
                    // mostRight.right 已经指向当前节点，第二次来到当前节点
                    // 恢复原来的树形结构
                    mostRight.right = null;
                }
            }

            System.out.println(cur.value);

            cur = cur.right;
        }
    }


    /**
     * 使用morris 遍历进行后序遍历
     *
     * @param head
     */
    public static void morrisPos(Node head) {
        if (head == null) {
            return;
        }

        Node cur = head;
        Node mostRight = null;

        while (cur != null) {

            mostRight = cur.left;

            if (mostRight != null) {
                while (mostRight.right != null) {
                    mostRight = mostRight.right;
                }

                if (mostRight.right == null) {
                    mostRight.right = cur;
                    cur = cur.left;
                    continue;
                } else {
                    mostRight.right = null;

                    // 有左子树的节点第二次到达时
                    // 逆序打印当前节点左子树的右边界
                    printEdge(cur.left);
                }
            }
            cur = cur.right;
        }

        // 最后逆序打印整个树的有边界
        printEdge(head);
    }

    /**
     * 逆序打印左子树的右边界
     *
     * @param x
     */
    private static void printEdge(Node x) {
        // 从左子树的根节点开始，反转右边界单链表
        // 获取右边界的最右节点
        Node tail = reverseEdge(x);

        // 从右边界的最右节点 开始遍历单链表，打印
        Node cur = tail;
        while (cur != null) {
            System.out.println(cur.value);
            cur = cur.right;
        }

        // 从右边界的最右节点开始,反转右边界单链表
        // 恢复树形结构
        reverseEdge(tail);
    }

    /**
     * 反转一个单链表的方向
     *
     * @param cur 头节点
     * @return 尾节点
     */
    private static Node reverseEdge(Node cur) {
        // 头节点变成指向尾巴节点
        Node pre = null;
        Node next = null;

        // 跳出条件，当前节点指向null
        while (cur != null) {
            // 获取下一个节点
            next = cur.right;
            // 当前节点指向前一个节点
            cur.right = pre;
            // 当前节点变为下一个，前一个节点
            pre = cur;
            // 下一个节点变为当前节点
            cur = next;
        }

        return pre;
    }

    /**
     * 使用morris进行是中序遍历，来判断一棵树是不是搜索二叉树
     * @param head
     */
    public static boolean isBST(Node head) {
        if (head == null) {
            // 空树是搜索二叉树
            return true;
        }

        Node cur = head;
        Node mostRight = null;

        // 前一个遍历到的节点的值
        int preValue = Integer.MIN_VALUE;


        while (cur != null) {
            // mostRight是cur左孩子
            mostRight = cur.left;

            if (mostRight != null) {
                // 有左子树
                while (mostRight.right != null && mostRight.right != cur) {
                    mostRight = mostRight.right;
                }

                // mostRight变成了cur左子树上，最右的节点
                if (mostRight.right == null) {
                    // 第一次来到cur

                    // 该叶节点的右指针指向当前节点
                    mostRight.right = cur;
                    // 当前节点指针指向当前节点的左节点
                    cur = cur.left;
                    continue;
                } else {
                    // mostRight.right 已经指向当前节点，第二次来到当前节点
                    // 恢复原来的树形结构
                    mostRight.right = null;
                }
            }

            if (cur.value <= preValue) {
                return false;
            }

            preValue = cur.value;

            cur = cur.right;
        }


        Math.max(1,2);
        return true;
    }
}
